﻿
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>

using namespace std;

/*

地址  https://leetcode.cn/problems/largest-rectangle-in-histogram/

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10


示例 2：
输入： heights = [2,4]
输出： 4
 

提示：
1 <= heights.length <=10^5
0 <= heights[i] <= 10^4



class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size(), ans = 0;
        heights.push_back(-1);
        // 为了算法书写方便，在数组末尾添加高度 -1
        // 这会使得栈中所有数字在最后出栈。

        stack<int> st;
        for (int i = 0; i <= n; i++) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int cur = st.top();
                st.pop();

                if (st.empty())
                    ans = max(ans, heights[cur] * i);
                else
                    ans = max(ans, heights[cur]
                            * (i - st.top() - 1));
            }
            st.push(i);
        }

        return ans;
    }
};

*/


/*
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int ans = 0;
        heights.push_back(-1);
        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int currIdx = st.top(); st.pop();
                if (st.empty()) {
                    ans = max(ans, heights[currIdx] * i);
                }
                else {
                    ans = max(ans, (i - st.top() - 1) * heights[currIdx]);
                }
            }
            st.push(i);
        }
        cout << ans << endl;
        return ans;
    }
};
*/

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size();
        vector<int> leftmin(len, -1);  vector<int> rightmin(len, len);
        stack<int> st;
        for (int i = 0; i < len; i++) {
            while (!st.empty() && heights[i] <= heights[st.top()]) { st.pop();}
            if (!st.empty()) { leftmin[i] = st.top();}
            st.push(i);
        }

        while (!st.empty()) { st.pop(); }

        for (int i = len - 1; i >= 0; i--) {
            while (!st.empty() && heights[i] <=  heights[st.top()]) { st.pop(); }
            if (!st.empty()) {  rightmin[i] = st.top();}
            st.push(i);
        }

        int ans = 0;

        for (int i = 0; i < len; i++) {
            int left = leftmin[i];   int right = rightmin[i];
            ans = max(ans, ( right- left- 1) * heights[i]);              
        }

        cout << ans << endl;
        return ans;
    }
};

//
//int main() {
//    Solution s;
//    vector<int> v{ 2,4 };
//    s.largestRectangleArea(v);
//    return 0;
//}